package org.hhchat.leetcode.sort;

import org.hhchat.leetcode.dataStruct.Interval;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * Created this one by HMH on 2017/5/29.
 * 存在交集就合并，需要处理流程：先排序、检测交叉、合并集合。
 */
public class code56 {
    public static class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            if (intervals.size() <= 1) {
                return intervals;
            }
            Collections.sort(intervals, new Comparator<Interval>() {
                @Override
                public int compare(Interval o1, Interval o2) {
                    return o1.start > o2.start ? 1 : o1.start == o2.start?0:-1;
                }
            });
            for (int i = 0; i < intervals.size()-1; i++) {
                if (hasIntersection(intervals.get(i), intervals.get(i + 1))) {
                    intervals.get(i).end = Math.max(intervals.get(i).end,intervals.get(i + 1).end);
                    intervals.remove(i + 1);
                    i--;
                }
            }
            return intervals;
        }

        public boolean hasIntersection(Interval i1, Interval i2) {
            return i1.end >= i2.start;
        }
    }
    public static void main(String[] args){
        Interval i1 = new Interval(1,4);
        Interval i2 = new Interval(2,3);
        List<Interval> list = new ArrayList<>();
        list.add(i1);
        list.add(i2);
        Solution solution = new Solution();
        list = solution.merge(list);
        System.out.println(list);

    }
}
